package com.lihepeng.leecode.sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 * <p>
 * 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 * <p>
 * 注意:
 * 不能使用代码库中的排序函数来解决这道题。
 * <p>
 * 示例:
 * <p>
 * 输入: [2,0,2,1,1,0]
 * 输出: [0,0,1,1,2,2]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sort-colors
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution75 {
    /**
     * 使用一个指针方法 针对数据里面的元素进行移动
     * 首先移动0 元素，如果碰到0 就将元素位置和0d的位置进行交换
     * 然后遍历1 的位置，如果碰到之后就将头部位置和当前元素进行交换，
     * 这样顺序就会被固定下来
     *
     * @param nums
     */
    public void sortColors(int[] nums) {
        // 头部索引的位置
        int ptr = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                // 交换头部和当前元素的位置
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr++] = temp;

            }

        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 1) {
                // 交换头部和当前元素的位置
                int temp = nums[i];
                nums[i] = nums[ptr];
                nums[ptr++] = temp;

            }

        }

    }

    // 使用双指针遍历移动元素顺序
    public void sortColors01(int[] nums) {
        int n = nums.length;
        int p0 = 0, p2 = n - 1;
        for (int i = 0; i <= p2; i++) {
            while (i <= p2 && nums[i] == 2) {
                swap(nums, i, p2--);
            }
            if (nums[i] == 0) {
                swap(nums, p0++, i);
            }
        }
    }

    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }

    @Test
    public void runTest() {
        int[] nums = {0, 1, 0, 2, 1, 0, 1, 0, 2, 0};
        sortColors(nums);
        System.out.println(Arrays.toString(nums));
    }

    @Test
    public void runTest02() {
        int[] nums = {0, 1, 0, 2, 1, 0, 1, 0, 2, 0};
        sortColors01(nums);
        System.out.println(Arrays.toString(nums));
    }

    @Test
    public void runTest01() {
        for (int i = 0; i < 10; ++i) {
            System.out.println(i);
        }
    }

}
